package com.grakol.algorithm.samples;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * Implements the following 'connectivity' algorithm (for oriented connection): 
 * Consider a sequence of pairs of objects - the pair p-q means "p is connected to q." 
 * The relation "is connected to" is transitive: if p is connected to q, and q is connected to r, then p is connected to r.
 * When the program inputs a pair p-q, it should add the pair to the sequence only if the pairs it has seen so far 
 * do not imply that p is connected to q. If the previous pairs do imply that p is connected to q, then the program should 
 * ignore p-q and should proceed to input the next pair (see R. Sedgewick, Algorithms in Java, 3rd ed., Addison Wesley, 2002).
 *  
 * @author LK
 *
 * @param <E> element type - implements {@code Comparable<E>} interface and appropriate 
 * {@code equals()} and @{code toString()} method.
 */
public class Connectivity<E extends Comparable<E>> {
	/**
	 * Nested class that implements 'connection' object.
	 * 
	 * @param <E> element type - implements {@code Comparable<E>} interface and appropriate 
	 * {@code equals()} and @{code toString()} methods.
	 */
	public static class Conn<E extends Comparable<E>> {
		// attributes
		private E _firstElem;
		private E _lastElem;
		private List<E> _path = new ArrayList<E>();
		
		/**
		 * Constructs new connection object from given first and last elements.
		 * 
		 * @param firstElem The given first element.
		 * @param lastElem The given last element.
		 */
		public Conn( E firstElem, E lastElem ) {
			_firstElem = firstElem;
			_lastElem = lastElem;
		}
		/**
		 * Constructs new connection object from a given list of interconnected elements. 
		 * If the given list contains more than 2 elements, the new connection object will 
		 * represent implied connection.
		 * 
		 * @param path the given list of elements connected to each other.
		 */
		public Conn( List<E> path ) {
			this( path.get( 0 ), path.get( path.size() - 1 ) );
			if( path.size() > 2 )
				_path = new ArrayList<E>( path.subList( 1, path.size() - 1 ) );
		}
		/**
		 * Copy constructor.
		 * 
		 * @param conn The given connection object to be copied. 
		 */
		public Conn( Conn<E> conn ) {
			_firstElem = conn.getFirstElem();
			_lastElem = conn.getLastElem();
			_path = new ArrayList<E>( conn.getPath() );
		}
		/**
		 * Returns the first connection element.
		 * 
		 * @return the first connection element.
		 */
		public E getFirstElem() {
			return _firstElem;
		}
		/**
		 * Returns the last connection element.
		 * 
		 * @return the last connection element.
		 */
		public E getLastElem() {
			return _lastElem;
		}
		/**
		 * Returns the list of elements connecting the first and the last elements of this connection object
		 * (for implied connection).
		 * 
		 * @return the list of elements connecting the first and the last elements of this connection object.
		 */
		public List<E> getPath() {
			return _path;
		}
		/**
		 * Returns {@code true} if this connection object represents direct (not implied) connection.
		 * 
		 * @return {@code true} if this connection object represents direct (not implied) connection.
		 */
		public boolean isImplied() {
			return _path.size() > 0;
		}
		
		/**
		 * Returns {@code true} if both ends of the given connection object are equal to 
		 * corresponding ends of this connection object.
		 * 
		 * @return {@code true} if both ends of the given connection object are equal to 
		 * corresponding ends of this connection object.
		 */
		@SuppressWarnings("unchecked")
		@Override
		public boolean equals( Object other ) {
			if( ! (other instanceof Conn) ) 
				return false;
			Conn<E> otherConn = null;
			try {
				otherConn = (Conn<E>)other;
			} catch( Exception e ) {
				return false;
			}
			return getFirstElem().compareTo( otherConn.getFirstElem() ) == 0 
					&& getLastElem().compareTo( otherConn.getLastElem() ) == 0;
		}
		
		@Override
		public int hashCode() {
			return 31 + _firstElem.hashCode() + _lastElem.hashCode();
		}
		
		/**
		 * Returns {@code [p->q]} for direct connections and {@code (p->...->q)} for implied connections.
		 * 
		 * @return {@code [p->q]} for direct connections and {@code (p->...->q)} for implied connections.
		 */
		@Override
		public String toString() {
			StringBuilder buffer = new StringBuilder();
			if( isImplied() )
				buffer.append( '(' );
			else
				buffer.append( '[' );
			buffer.append( getFirstElem().toString() ).append( "->" );
			if( isImplied() ) {
				for( E e : _path ) 
					buffer.append( e.toString() ).append( "->" );
			}
			buffer.append( getLastElem().toString() );
			if( isImplied() )
				buffer.append( ')' );
			else
				buffer.append( ']' );
			return buffer.toString();
		}
		
	} // end of Conn<E>

	// attributes
	private HashSet<Conn<E>> _connRegistry = new HashSet<Conn<E>>();
	private HashMap<E, List<Conn<E>>> _connMap = new HashMap<E, List<Conn<E>>>();
	
	/**
	 * Adds connection between given first and last objects, if no direct or implied 
	 * connection already exists between the given objects. If a new connection has been 
	 * added, returns an empty string, otherwise returns a string representing existing 
	 * connection.
	 * 
	 * @param firstElem the given first object.
	 * @param lastElem the given last object.
	 * @return an an empty string, if a new connection has been added, otherwise - 
	 * a string representing existing connection.
	 */
	public String addConn( E firstElem, E lastElem ) {
		// check existing conn firstElem->lastElem
		Conn<E> conn = new Conn<E>( firstElem, lastElem );
		if( _connRegistry.contains( conn ) ) {
			return conn.toString();
		}
		String pathString = "";
		// try to find path firstElem->lastElem from existing conns
		List<E> path = findPath( firstElem, lastElem );
		if( path != null ) {
			conn = new Conn<E>( path );
			pathString = conn.toString();
		}
		// add new conn firstElem->lastElem
		registerConn( conn );
		return pathString;
	}
	/**
	 * Prints current registry of direct connections.
	 */
	public void printRegistry() {
		System.out.println( "> Connection registry (" + _connRegistry.size() + ") =>" );
		for( Conn<E> conn : _connRegistry )
			if( ! conn.isImplied() )
				System.out.println( ">> " + conn.toString() );
	}
	/**
	 * Returns list of interconnected elements connecting given first and last objects. 
	 * If no implied connection can be found, returns an empty list.
	 * 
	 * @param firstElem the given first object.
	 * @param lastElem the given last object.
	 * @return list of interconnected elements connecting given first and last objects or  
	 * empty list, if no implied connection can be found.
	 */
	private List<E> findPath( E firstElem, E lastElem ) {
		List<E> path = null;
		List<Conn<E>> connList = _connMap.get( firstElem );
		if( connList != null ) {
			for( Conn<E> conn : connList ) {
				if( conn.getLastElem().compareTo( lastElem ) == 0 ) {
					path = new ArrayList<E>();
					path.add( firstElem );
					path.add( lastElem );
					break;
				} else {
					List<E> tail = findPath( conn.getLastElem(), lastElem );
					if( tail != null ) {
						path = new ArrayList<E>();
						path.add( firstElem );
						path.addAll( tail );
						break;
					}
				}
			}
		}
		return path;
	}
	/**
	 * Adds a given connection object to the connection registry.
	 * 
	 * @param conn the given connection object to be added.
	 */
	private void registerConn( Conn<E> conn ) {
		// add mapping for conn.firstElem
		List<Conn<E>> list = _connMap.get( conn.getFirstElem() );
		if( list == null ) {
			list = new ArrayList<Conn<E>>();
			_connMap.put( conn.getFirstElem(), list );
		}
		list.add( conn );
		_connRegistry.add( conn );
	}
	/**
	 * Finds existing direct or implied connection between given first and last objects. 
	 * If no connection can be found, returns {@code null}.
	 * 
	 * @param firstElem the given first object.
	 * @param lastElem the given last object.
	 * @return existing direct or implied connection between given first and last objects 
	 * or {@code null}, if no connection can be found.
	 */
	public Conn<E> findConn( E firstElem, E lastElem ) {
		Conn<E> found = null;
		for( Conn<E> conn : _connRegistry )
			if( conn.getFirstElem().compareTo( firstElem ) == 0 
				&& conn.getLastElem().compareTo( lastElem ) == 0 ) {
				found = conn;
				break;
			}
		if( found == null ) {
			// try to find path firstElem->lastElem from existing conns
			List<E> path = findPath( firstElem, lastElem );
			if( path != null ) 
				found = new Conn<E>( path );
		}
		return found;
	}

}
